# Best Treasure Value
def get_treasures(ts,ws,t):
    w=0
    pre_value=[]
    for i in range(len(ts)):
        pre_value.append([ts[i],ws[i],ts[i]/ws[i]])
    pre_value.sort(key=lambda d:d[2],reverse=True)
    for i in range(len(pre_value)):
        if pre_value[i][1]<=t:
            w+=pre_value[i][0]
            t-=pre_value[i][1]
        else:
            w+=pre_value[i][2]*t
            break
    return w

# distribute biscuits to kids
def distribute(kids,biscuits):
    n=len(kids)
    def give(kid,biscuit):
        while len(kids) > 0 and len(biscuits) > 0:
            kid=min(kids)
            biscuit=min(biscuits)
            if kid <= biscuit:
                kids.remove(kid)
                biscuits.remove(biscuit)
            else:
                biscuits.remove(biscuit)
                if len(biscuits) > 0:
                    return give(kid,biscuit+min(biscuits))
        return (biscuit-kid) >= 0
    give(min(kids),min(biscuits))
    count=n-len(kids)
    return count

# lemonade change
def change(collection):
    changes=[]
    for money in collection:
        if money == 20:
            try:
                changes.remove(10)
                changes.remove(5)
            except Exception:
                try:
                    for i in range(3):
                        changes.remove(5)
                except Exception:
                    return False
        if money == 10:
            try:
                changes.remove(5)
            except Exception:
                return False
            changes.append(money)
        if money == 5:
            changes.append(money)
    return True

def lemonadeChange(bills):
    remain_5=[]
    remain_10=[]
    for i in range(len(bills)):
        if bills[i] == 5:
            remain_5.append(1)
        elif bills[i] == 10:
            if not remain_5:
                return False
            remain_5.pop()
            remain_10.append(1)
        else:
            remain=15
            if len(remain_10) >= 1:
                remain-=10
                remain_10.pop()
            while len(remain_5) > 0 and remain > 0:
                remain-=5
                remain_5.pop()
            if remain > 0:
                return False
    return True

# dual dispatching
def twoCitySchedCost(costs):
    min_costs=0
    N=len(costs)//2
    costs.sort(key=lambda x:x[0]-x[1])
    min_costs+=sum([ costs[i][0] for i in range(N) ])
    min_costs+=sum([ costs[i][1] for i in range(N,2*N) ])
    return min_costs

# jump game
def reach_goal(array):
    if 0 not in array:
        return True
    end=array.index(0)
    subarray=array[:end]
    for j in range(end-1,-1,-1):
        n=subarray[j]
        if n > end-j:
            return(reach_goal(array[end+1:]))
    return False

def canJump(array):
    if 0 not in array:
        return True
    if len(array) < 2:
        return True
    max_distance=0
    for i in range(len(array)-1):
        if i <= max_distance:
            max_distance=max(i+array[i],max_distance)
        else:
            break
    return max_distance >= len(array)-1

def canJump2(array):
    max_distance=0
    for i in range(len(array)):
        if i <= max_distance:
            max_distance=max(i+array[i],max_distance)
            if max_distance >= (len(array)-1):
                return True
        else:
            break
    return False

# couple hand in hand
def minSwapsCouples(seats):
    if len(seats) <= 2:
        return 0
    count=0
    for i in range(0,len(seats),2):
        couple_id=seats[i]^1
        if seats[i+1] == couple_id:
            continue
        count+=1
        for j in range(i+2,len(seats)):
            if seats[j] == couple_id:
                seats[i+1],seats[j]=seats[j],seats[i+1]
                break
    return count

# deliver candy
def deliver_candy(kids):
    candys=[1]*len(kids)
    for i in range(1,len(kids)-1):
        mid=kids[i]
        left=kids[i-1]
        right=kids[i+1]
        if mid > left and mid > right:
            candys[i]+=1
    for i in range(1,len(kids)):
        mid=kids[i]
        left=kids[i-1]
        if mid > left and candys[i] <= candys[i-1]:
            candys[i]=candys[i-1]+1
    if kids[0] > kids[1] and candys[0] <= candys[1]:
        candys[0]=candys[1]+1
    return sum(candys)
